package 排序;

public class BinarySearch {
	/**
	 * 查询元素的索引
	 * 
	 * @param array
	 * @param element
	 * @return
	 */
	public static int indexOf(Integer[] array, Integer element) {
		if (array == null || array.length == 0) return -1;
		int begin = 0;
		int end = array.length;
		while (begin < end) {
			int mid = (begin + end) >> 1;
			if (element < array[mid]) {
				end = mid;
			} else if (element > array[mid]) {
				begin = mid + 1;
			} else {
				return mid;
			}
		}
		return -1;
	}

	/**
	 * 查询元素element应该被插入的索引位置
	 * 该索引对应第一个比element大的元素
	 * [1, 2, 3, 3, 3, 4, 5] 插入3时, 应该返回index = 5
	 * 
	 * @param array
	 * @param element
	 * @return
	 */
	public static int search(Integer[] array, Integer element) {
		if (array == null || array.length == 0) return -1;
		int begin = 0;
		int end = array.length;
		while (begin < end) {
			int mid = (begin + end) >> 1;
			if (element < array[mid]) {
				end = mid;
			} else {
				begin = mid + 1;
			}
		}
		return begin;
	}

	public static void main(String[] args) {
		Integer[] arr = new Integer[] { 1, 2, 3, 3, 3, 4, 5};
		System.out.println(search(arr, 0) == 0);
		System.out.println(search(arr, 6) == 7);
	}
}
